題目練習

請ChatGPT幫我根據本週學習到的類型，隨機出幾道題目。

121. Best Time to Buy and Sell Stock

要求我們在一個股票價格的列表中找出最大收益，只能買一次股票，然後賣一次股票，並且要確保賣的時間在買的時間之後。

class Solution:
    def maxProfit(prices):
        min_price = int
        max_profit = 0

        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > max_profit:
                max_profit = price - min_price

        return max_profit

206. Reverse Linked List

給定一個單向鏈表，將其節點的順序反轉，並返回反轉後的鏈表頭節點。

def reverseList_while(self, head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    curr = head

    while curr:
        next_temp = curr.next  # 暫存當前節點的下一個節點
        curr.next = prev  # 將當前節點的 next 指向前一個節點
        prev = curr  # prev 向前移動到當前節點
        curr = next_temp  # curr 向前移動到下一個節點

    return prev  # 最終 prev 會指向新的頭節點

這題好像也可以用遞迴做。

75. Sort Colors

給定一個包含 0、1 和 2 的陣列，你需要對這個陣列進行就地排序，使得相同的數字被分組排列，順序是 0, 1, 2。重要的是，你必須就地修改陣列，而不能使用額外的空間（除了常數級別的額外空間）。

題目需求

• 輸入: 一個只包含 0、1 和 2 的整數陣列 nums。
• 輸出: 你需要就地修改這個陣列，將它排序為 0, 1, 2。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        buckets = [[] for _ in range(3)]

        for n in nums:
            buckets[n].append(n)

        nums.clear()
        nums.extend([n for sublist in buckets for n in sublist])

小結

第一週挑戰接近尾聲了，即將進入第二個學習主題——Tree，本週透過較短的影片和部落格文章學習了許多基本概念，在解題上巧妙地運用這些概念，能夠顯著提升運算效能，這階段主要是學習基本概念，打好基礎，接下來的挑戰將運用這些概念來構建適用於不同場景的演算法。

這些演算法就像工具箱中的工具，根據不同的問題場景，我們可以靈活地選擇並使用最合適的演算法。在接下來的學習中，我期待能更深入地理解如何將這些算法應用到實際場景，並且解決更多具有挑戰性的問題。隨著知識的積累，這些工具將不再是抽象的理論，而是實際解決問題的有力武器。期待第二週的Tree主題挑戰，看看如何在實戰中應用這些學到的技巧！